#include<vector>
#include<unordered_map>
#include<iostream>
using std::unordered_map;
using std::vector;


class Solution {
private:
    vector<int> dp;

public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size();
        dp = vector<int>(2001, 0);
        dp[num2idx(nums[0])] = 1;
        dp[num2idx(-nums[0])] = 1;
        for (int i = 1; i < n; i++) {
            int v = nums[i];
            vector<int> tmp(2001, 0);
            for (int j = 0; j < 2001; j++) {
                if (dp[j] > 0) {
                    tmp[j-v] += dp[j-v]+1;
                    tmp[j+v] += dp[j+v]+1;
                }
                
            }
            dp = tmp;
        }
        return dp[num2idx(target)];
    }

    int num2idx(int num) {
        return num + 1000;
    }
    

    
};